2004 TopCoder Open Online Round 1

Match Summary

Round Overview
Discuss this match

What is it called when you gather the best coders in the world at a single event? If you didn’t already know the answer, it’s called the TopCoder Open, and we are already in the thick of it. Online Round 1 further prunes the entry list, funneling 500 competitors into 200 slots. For some, Round 1 is a chance to surprise the crowds, gain a few ratings points, and be inducted into TopCoder’s elite. For others, it is purely strategic. Several reds use the round to survey their opponents, and determine which competitors will prove most troublesome in the future. tomek used Round 1 to remind everyone else who won last year. He whisked away the title in the waning seconds of the challenge round… and don’t think he didn’t plan it that way.

BadMazeStrategy

Used as: Division One - Level One:

Unlike most traversal problems encountered on TC, this one allowed movement along diagonals. That didn’t seem to bother most coders. The only added difficulty here was loop detection. Many of the solutions I saw had a large boolean matrix that marked off (row,col,direction) triplets. If such a triplet occurred again, a loop has been detected. An alternate method would be to count steps. If you end up taking more than 50*50*8 steps, you know you are in a loop (basically the pigeonhole principle applied to the previously described matrix).

This step counting method sparked a discussion between radeye and myself, that later spread to Chat Room 1, the round table, and even this write-up. The challenge was: “Build a 50 x 50 maze that requires the largest number of steps to reach the destination.” Eryx and ChristopherH have some elegant solutions.

BadParser

Used as: Division One - Level Two:

In BadParser you are given a binary tree, whose only guarantee is that an inorder traversal will produce the original expression. Unsurprisingly, the first thing done by most solutions was to inorder traverse the given tree. Once the original expression was obtained, parse it correctly to obtain the result. All worries about tree structure, overflow, and division by 0 were eliminated by the constraints. Since there were no parentheses in the expression, my parser greedily looks for the first occurrence of a ‘/’ or a ‘*’. Otherwise, it settles for the first ‘+’ or ‘-’. Then it applies the operation to its neighboring operands, thus simplifying the expression. This process is repeated until only a single value remains, namely the result. Java code follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
String ops = "*+-/";

//inorder traversal modified to add helpful spaces
String inorder(String[] tree, int node) {
  if (ops.indexOf(tree[node].charAt(0)) != -1) {
    String[] toks = tree[node].split(" ");
    String ret = inorder(tree, Integer.parseInt(toks[1]));
    ret += " " + toks[0] + " ";
    return ret + inorder(tree, Integer.parseInt(toks[2]));
  } else return tree[node];
}

//Executed after the inorder traversal
int eval(String expr) {
  if (expr.indexOf(' ') == -1) return Integer.parseInt(expr);
  ArrayList al = new ArrayList(Arrays.asList(expr.split(" ")));
  while (true) {
    if (al.size() == 1) return Integer.parseInt(al.get(0) + "");
    int high = al.indexOf("*");
    if (high < 0 || (al.indexOf("/") > -1 && al.indexOf("/") < high))
      high = al.indexOf("/");
    if (high == -1) high = 1;
    String B = al.remove(high + 1) + "", OP = al.remove(high) + "", A = al.remove(high - 1) + "";
    int a = Integer.parseInt(A), b = Integer.parseInt(B), c = 0;
    if (OP.equals("*")) c = a * b;
    if (OP.equals("+")) c = a + b;
    if (OP.equals("-")) c = a - b;
    if (OP.equals("/")) c = a / b;
    al.add(high - 1, c + "");
  }
}

Find3Cheaters

Used as: Division One - Level Three:

The longest common subsequence (LCS) problem occurs in nearly every undergraduate algorithms text. To depart from the norm, this problem asks for the shortest common supersequence (SCS). Had there only been 2 strings, LCS and SCS have the same solution. In the 3-string case, a new method is required to solve SCS. Given 3 strings, the recursive solution I wrote computes the result by considering what characters can possibly begin a shortest common supersequence. After choosing a character, we are left we a smaller version of the same problem. The algorithm tries all potential characters (the only characters worth trying are at the front of the input strings), and uses memoization for speed. Java code follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int cache[][][];
String a, b, c;

//returns SCS for a.substring(pa),b.substring(pb),c.substring(pc)
int shortRec(int pa, int pb, int pc) {
  if (cache[pa][pb][pc] != -1) return cache[pa][pb][pc];
  int A = a.length(), B = b.length(), C = c.length();
  if (pa == A && pb == B && pc == C) return 0;
  int best = 1000000;
  //here i = 1 means I put the first char from String a in the supersequence
  //j and k denote the same things for Strings b and c respectively
  for (int i = 0; i <= 1; i++)
    for (int j = 0; j <= 1; j++)
      for (int k = 0; k <= 1; k++) {
        if (i + j + k == 0) continue;
        if (pa + i > A || pb + j > B || pc + k > C) continue;
        if (i > 0 && j > 0 && a.charAt(pa) != b.charAt(pb)) continue;
        if (i > 0 && k > 0 && a.charAt(pa) != c.charAt(pc)) continue;
        if (k > 0 && j > 0 && c.charAt(pc) != b.charAt(pb)) continue;
        best = Math.min(best, 1 + shortRec(pa + i, pb + j, pc + k));
      }
  return cache[pa][pb][pc] = best;
}

public int shortest(String a, String b, String c) {
  this.a = a;
  this.b = b;
  this.c = c;
  cache = new int[a.length() + 1][b.length() + 1][c.length() + 1];
  for (int i = 0; i < cache.length; i++)
    for (int j = 0; j < cache[i].length; j++)
      for (int k = 0; k < cache[i][j].length; k++) cache[i][j][k] = -1;
  return shortRec(0, 0, 0);
}